package JavaSE;
import java.util.Scanner;
//汉诺塔是一个经典的递归问题。
// 问题描述：有三根柱子A、B、C，A柱子上有n个盘子，从下到上按大小递减排列。
// 要将所有盘子从A移动到C，每次只能移动一个盘子，且大盘子不能放在小盘子上面。
//解题思路：
//如果只有一个盘子，直接将其从源柱移到目标柱
//否则：
//先将n-1个盘子从源柱移到辅助柱
//将第n个盘子从源柱移到目标柱
//最后将n-1个盘子从辅助柱移到目标柱
public class time_2025_07_04用递归解决汉诺塔问题 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String start = "A";
        String middle = "B";
        String end = "C";
        hanoi(n,start,middle,end);
    }

    public static void hanoi(int n,String start,String middle,String end){
        if(n==1){
            System.out.println("将第一个盘子从"+start+"移动到"+end);
            return;
        }

        hanoi(n-1,start,end,middle);
        System.out.println("将第"+n+"个盘子从"+start+"移动到"+end);
        hanoi(n-1,middle,start,end);
    }
}
